package leetcode.top100;


import utils.TreeNode;
import utils.TreeUtil;

import java.util.Stack;

/**
 * @since 2019/12/18 0018 下午 8:31
 */
public class Code617_MergeTwoBT {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(3);
        t1.right = new TreeNode(2);
        t1.left.left = new TreeNode(5);
        t1.left.left.left = new TreeNode(9);
        TreeUtil.printTree(t1);
        TreeNode t2 = new TreeNode(2);
        t2.left = new TreeNode(1);
        t2.right = new TreeNode(3);
        t2.left.right = new TreeNode(4);
        t2.right.right = new TreeNode(7);
        TreeUtil.printTree(t2);
        t1 = mergeTrees(t1,t2);
        TreeUtil.printTree(t1);

    }
    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1 == null || t2 == null) return t1 == null? t2:t1;
        return process(t1,t2);
    }
    //方式1：新建树
    private static TreeNode process1(TreeNode t1,TreeNode t2){
        if(t1 == null || t2 == null){
            return t1 == null ? new TreeNode(t2.val) : new TreeNode(t1.val);
        }
        TreeNode root;
        root = new TreeNode(t1.val+t2.val);
        root.left = process(t1.left,t2.left);
        root.right = process(t1.right,t2.right);
        return root;
    }
    //方式2：都合并到t1树上。
    private static TreeNode process2(TreeNode t1,TreeNode t2){
        if(t1 == null || t2 == null){
            return t1 == null ? new TreeNode(t2.val) : new TreeNode(t1.val);
        }
        t1.val += t2.val;
        t1.left = process2(t1.left,t2.left);
        t1.right = process2(t1.right,t2.right);
        return t1;
    }
    /**
     * 方式3：迭代版合并到一颗树上
     */
    private static TreeNode process(TreeNode t1,TreeNode t2){
        Stack<TreeNode[]> stack = new Stack<>();
        stack.push(new TreeNode[]{t1,t2});
        while (!stack.isEmpty()){
            TreeNode[] root = stack.pop();
            //root[1]可能为空，是由上次迭代的root[1].right或者root[1].left为空导致的
            //root[0]不可能为空，如果root[1]为空的话，root[0]之后不用更改了，直接返回。
            if(root[1] == null){
                continue;
            }
            //root[0] and root[1] both not null,合并到t1上。
            root[0].val += root[1].val;
            //in order处理

            //如果t1的右孩子为空，直接把t2的右孩子给t1.stack没有入栈不会处理了。
            if(root[0].right == null){
                root[0].right = root[1].right;
            }else {
                //不为空，入栈。注意root[1].right可能为空，所以在上面要判断root[1]是否为空
                stack.push(new TreeNode[]{root[0].right,root[1].right});
            }
            //如果t1的左孩子为空，直接把t2的左孩子给t1.stack没有入栈不会处理了。
            if(root[0].left == null){
                root[0].left = root[1].left;
            }else {
                //不为空，入栈。注意root[1].left可能为空，所以在上面要判断root[1]是否为空
                stack.push(new TreeNode[]{root[0].left,root[1].left});
            }

        }
        return t1;
    }



}
